//#include <iostream>
//#include <string>
//using namespace std;
//
//const int N = 50;
//
//string a[50];
//string b[50];
//pair <int, string> ccc[60];
//int aaa = 0;
//int bbb = 0;
//
//int n;
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        int x;
//        string y;
//        cin >> x >> y;
//        ccc[i].first = x;
//        ccc[i].second = y;
//
//        if (x == 1)
//        {
//            a[++aaa] = y;
//        }
//        else
//        {
//            b[++bbb] = y;
//        }
//    }
//    for (int i = 1; i <= n / 2; i++)
//    {
//        cout << ccc[i].second << " ";
//        if (ccc[i].first == 0)
//        {
//            cout << a[aaa--] << endl;
//        }
//        else if (ccc[i].first == 1)
//        {
//            cout << b[bbb--] << endl;
//        }
//    }
//
//    return 0;
//}



//#include <stdio.h>
//#include <string.h>
//
//int main()
//{
//    char str[100];
//    while (scanf("%s", str) != EOF)
//    {
//        int x = (strlen(str) / 3 - 1) * 3;
//        printf("%s", str + x);
//    }
//
//    return 0;
//}



//#include <iostream>
//#include <map>
//using namespace std;
//
//const int N = 1010;
//map<int, int> mp;
//
//int main()
//{
//    int n;
//    cin >> n;
//    int a;
//
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a;
//        for (int j = 1; j <= a; j++)
//        {
//            int x;
//            cin >> x;
//            mp[x]++;
//        }
//    }
//    int mm = 0;
//    int num = 0;
//    for (auto ch : mp)
//    {
//        if (ch.second > mm)
//        {
//            num = ch.first;
//            mm = ch.second;
//        }
//        else if (ch.second == mm)
//        {
//            if (ch.first > num)
//            {
//                num = ch.first;
//            }
//        }
//    }
//    //cout << mp[233] << endl;
//    cout << num << " " << mp[num] << endl;
//    return 0;
//}



//#include <iostream>
//#include <string>
//#include <cmath>
//using namespace std;
//
//pair<string, int> a[10010];
//
//int main()
//{
//    int n;
//    cin >> n;
//    int sum = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i].first >> a[i].second;
//        sum += a[i].second;
//    }
//
//    sum /= n;
//    sum /= 2;
//    int num = 1;
//    int mm = abs(a[1].second - sum);
//    for (int i = 2; i <= n; i++)
//    {
//        if (abs(a[i].second - sum) < mm)
//        {
//            mm = abs(a[i].second - sum);
//            num = i;
//        }
//    }
//
//    cout << sum << " " << a[num].first;
//
//    return 0;
//}




//#include <stdio.h>
//
//int main()
//{
//    int a;
//    scanf("%d", &a);
//    int gg = 0;
//    int tt = 0;
//    int i = 0;
//    for (i = 0; i + 10 <= a; i += 10)
//    {
//        if (gg >= tt)
//        {
//            gg += 10 * 3;
//            tt += 10 * 9;
//        }
//        else
//        {
//            if (i + 30 <= a)
//            {
//                gg += 3 * 30;
//                i += 20;
//            }
//            else
//            {
//                gg += (a - i) * 3;
//                break;
//            }
//        }
//    }
//
//    if (gg > tt)
//    {
//        printf("@_@ %d", gg);
//
//    }
//    else if (gg < tt)
//    {
//        printf("^_^ %d", tt);
//    }
//    else
//    {
//        printf("-_- %d", gg);
//    }
//    return 0;
//}


//int cmp(const void* a, const void* b)
//{
//    return (*((float*)a)) - (*((float*)b));
//}
//
//ElementType Median(ElementType A[], int N)
//{
//    qsort(A, N, sizeof(float), cmp);
//    return A[(N + 1) / 2 - 1];
//}


//void dectobin(int n)
//{
//    int a[10000];
//    int cnt = 0;
//    int tmp = n;
//    while (tmp > 0)
//    {
//
//        a[cnt++] = (n >> cnt) & 1;
//        tmp >>= 1;
//    }
//    for (int i = cnt - 1; i >= 0; i--)
//    {
//        printf("%d", a[i]);
//    }
//}